package LeetCode;

/**
 * @Classname LC740
 * @Description // https://leetcode-cn.com/problems/delete-and-earn/ 动态规划 删除并获得点数 等价于 打家劫舍4
 * 在偷了三处村庄后这个小偷又来到了第四个村庄进行偷窃。他发现这个村庄得居民变得聪明了，将房屋打乱了顺序，并且报警器也变得更加得灵敏，在偷了5块钱后，偷6块钱跟4块钱它都会报警，但是由于性能的提升，报警器也有"bug", 那就是偷了5块钱后继续偷5块钱报警器不会触发。这小偷还是个程序员呢！于是小偷产生了以下的思路。
 *
 * 作案手法
 * 他聪明的将房屋进行了排序，写在了自己的记事本里。由于发现了报警器的"bug", 对于所有为5块钱的房屋都只记录了一个，还记录了其数字以免错过。然后在他偷窃5块钱房屋的时候他会将所有对应的房屋都偷窃完。
 * 因此在他的记事本上写了两个东西：
 * 排序后的房屋金额，注意这里没有重复的！
 * 各个房屋金额所对应的房屋数量(他用的哈希表，眼睛找起来更快)
 * 做完以上步骤后他开始偷窃了，每次偷完上一个房屋时都记录下上一次房屋偷窃了多少钱。
 * 在偷窃下一个房屋时，如果发现这次的房屋金额如果刚好等于上一次的偷窃金额+1时，他就看是偷当前的房屋金额加上前前次的房屋金额大，还是上一次偷窃的房屋金额大。
 * dp[i] = max(dp[i-1], dp[i-2] + dp[i] * m[dp[i]]);
 * 如果这一个房屋的金额比上一次偷窃的金额要比1还大时他知道不会出发报警器，因此他就将上次的钱也一起带过来了。
 * dp[i] = dp[i-1] + dp[i] * m[dp[i]];

 * @Date 2021/5/5 23:44
 * @Created by yin
 */
public class LC740 {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    public int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}
